#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/mman.h>
#include <string.h>
#include <errno.h>

#include "kvdb.h"
#include "inner.h"

#define FILE_HEADER_LEN  PAGE_SIZE // 4KB

#define OK        0
#define PAGE_DELETED    1   // 删除记录 && 页也删除了
#define REC_NOT_FOUND   2   // 记录没有找到
#define PAGE_SPLITED    3   // 正在页分裂
#define REC_REPLACED    4   // 更新成功
#define REC_INSERTED    5   // 已经插入
#define FOUND_EXACT     6   // 准确找到
#define FOUND_GREATER   7   // 找到更多的


/*
 * TODO: to dump all items in the call stack
 */
void __kvdb_assert(int cond, const char *func, char *file, int line) {
    if (!cond) {
        perror("error");
        // https://blog.csdn.net/hxlawf/article/details/89383366
        fprintf(stderr, "assertion violation: %s:%d, func=%s(), errno=%d\n", file, line, func, errno);
        abort();
    }
}

/* 
 * dump a page header and all records in that page
 */
void _kvdb_dump_page(gpid_t gpid, struct page_s *p) {
    int i;
    fprintf(stderr, "kvdb_dump_page():\n");
    fprintf(stderr, "gpid = %lu\n", gpid);
    fprintf(stderr, "h.record_num = %u\n", p->h.record_num);
    fprintf(stderr, "h.flags = %x\n", p->h.flags);
    fprintf(stderr, "h.next = %lx\n", p->h.next);
    for (i = 0; i < (int) p->h.record_num; i++) {
        fprintf(stderr, "kv: i=%3d, k=%lu, v=%lu\n", i, p->rec[i].k, p->rec[i].v);
    }
    fprintf(stderr, "\n");
}

/*
 * dump a page which did not open before
 * 转储之前未打开的页面
 */
void kvdb_dump_page(kvdb_t d, gpid_t gpid) {
    // 分配器链表中的节点
    pg_t pg;
    // 物理节点
    struct page_s *p;
    // 通过全局唯一ID获得 一页
    pg = get_page(d, gpid);
    // 再从页中获得 buf
    p = get_page_buf(d, pg);
    // 刷盘
    _kvdb_dump_page(gpid, p);
    // free to busy 链表
    put_page(d, pg);
}

/*
 * dump the database file header
 */
void kvdb_dump_head(kvdb_t d) {
    fprintf(stderr, "kvdb header: \n");
#define pr(f) fprintf(stderr, "%10s: %lu\n", #f, (uint64_t)d->h->f)
    pr(record_num);
    pr(root_gpid);
    pr(level);
    pr(total_pages);
    pr(spare_pages);
#undef pr
    fprintf(stderr, "\n");
}

/*
 * dump the whole B+ Tree in the database file
 * 只能传入 B+Tree 的根节点
 */
void kvdb_dump_tree(kvdb_t d, gpid_t gpid) {
    // 缓存节点
    pg_t pg;
    // 物理页
    struct page_s *p;
    int i;
    // 1️⃣缓存 2️⃣重新分配
    pg = get_page(d, gpid);
    // 具体物理页地址
    p = get_page_buf(d, pg);
    // 刷盘 buf
    _kvdb_dump_page(gpid, p);
    // 如果当前 page 是 非叶子节点
    if ((p->h.flags & PAGE_LEAF) == 0) {
        // 当前 page 页中记录总数
        for (i = 0; i < p->h.record_num; i++) {
            // 递归向下转存
            kvdb_dump_tree(d, p->rec[i].v);
        }
    }
    // 用完返回 free 列表中
    put_page(d, pg);
}

/*
 * dump all contents in the database
 */
void kvdb_dump(kvdb_t d) {
    fprintf(stderr, "\ndump the whole tree\n");
    kvdb_dump_head(d);
    // 肯定是树根
    kvdb_dump_tree(d, d->h->root_gpid);
    fprintf(stderr, "\n");
}

/*
 * open the database
 * TODO: we do not discriminate RDONLY and RDWR now, so may we could do it later.
 */
kvdb_t kvdb_open(char *name) {
    int fd;
    kvdb_t d;
    struct stat st;// 存放文件状态信息空间
    int ret;
    int new = 0;
    // 打开文件
    // fd = open(name, O_CREAT | O_RDWR | O_DIRECT, 0666);
    fd = open(name, O_CREAT | O_RDWR | O_DIRECTORY, 0666);
    if (fd < 0) {
        kvdb_assert(0);        // this failure seems most unlikely happens
        return NULL;
    }
    // 分配空间, 一个指针大小
    d = (kvdb_t) malloc(sizeof(*d));
    kvdb_assert(d != NULL);
    d->fd = fd;
    // fstat() 用来将参数 files 所指向的文件状态复制到 参数buf 所指向的结构中(struct stat),
    // fstat() 与 stat() 作用完全相同，不同之处在于传入的参数为已打开的文件描述符
    ret = fstat(d->fd, &st);
    kvdb_assert(ret == 0);
    // 文件大小 st.st_size < 4KB 也太小了
    if (st.st_size < FILE_HEADER_LEN) {
        // 预分配文件空间
        // 确保磁盘空间为分配给文件描述符 fd 所引用的文件从offset开始并继续len的范围内的字节字节
        // 在成功调用 posix_fallocate() 之后，可以确保写入指定范围内的字节不会因为磁盘空间不足导致失败
        ret = posix_fallocate(d->fd, 0, FILE_HEADER_LEN);
        if (ret != 0) {
            printf("posix_fallocate failed, errno = %d\n", ret);
            abort();
        }
        new = 1;
    }

    /*
     * mmap the file head and get its pointer saving in d->h
     * NOTICE: the flag be MAP_SHARED or modified data cannot be updated into the file
     */
    // metadata 文件元信息
    d->h = (struct file_header_s *) mmap(NULL, FILE_HEADER_LEN, PROT_READ | PROT_WRITE, MAP_SHARED, d->fd, 0);
    kvdb_assert(d->h != MAP_FAILED);

    /* if the database is created right before, we should initialize the header of the file */
    if (new) {
        char *m = (char *) &d->h->magic;
        strcpy(m, "kv@enmo");
        memset(d->h, 0, FILE_HEADER_LEN);
        d->h->record_num = 0;
        d->h->root_gpid = GPID_NIL;
        d->h->level = 0;
        d->h->total_pages = 0;
        d->h->spare_pages = 0;
    }

    d->h->file_size = st.st_size;
    // 加载chunk到内存
    init_allocator(d);
    // 缓存的双向链表，查找在这里
    init_cache(d);
    // 构建B+Tree
    return d;
}

int kvdb_close(kvdb_t db) {
    int ret;

    exit_cache(db);
    exit_allocator(db);

    ret = msync(db->h, PAGE_SIZE, MS_SYNC);
    kvdb_assert(ret == 0);

    ret = munmap(db->h, PAGE_SIZE);
    kvdb_assert(ret == 0);

    ret = fsync(db->fd);
    kvdb_assert(ret == 0);

    ret = close(db->fd);
    kvdb_assert(ret == 0);

    return 0;
}

/* 
 * bpt_make_root(): make the root page of the B+ Tree 
 *
 * This function would be called in two cases:
 * 1) when the first record is being inserted into the database which was created newly
 *    当第一条记录被插入到这个数据库中时，要作为树根，这么说，一般第一个chunk的第一个page是根
 * 2) when a page is fully filled with records and a new record is
 *    arrived to be inserted into that page, so we should split the 
 *    LEAF page, and it caused the root page full too. we must increase
 *    the level of the tree and create a new root page.
 *    页分裂，创建新树根
 */
static void bpt_make_root(kvdb_t d, int leaf) {
    struct page_s *p;
    pg_t pg;
    gpid_t gpid;
    // 新分配页面 4KB空间, 返回全局唯一 pageID
    gpid = alloc_page(d);
    kvdb_assert(gpid != GPID_NIL);
    // 设置为根节点
    d->h->root_gpid = gpid;
    d->h->level++; // 0 -> 1
    // 建立这个page的相关缓存索引
    // 并且新创建的page是安放在了 busy 链表中
    pg = get_page(d, gpid);
    // 真实的 page 页
    p = get_page_buf(d, pg);
    p->h.record_num = 0;
    p->h.flags = (leaf ? PAGE_LEAF : 0);
    p->h.next = GPID_NIL;
    // 用完返回 free 列表中
    put_page(d, pg);
}

/* 
 * find a key in a page, return the index of the record which
 * 二分法 找到 小于等于 k 的最佳索引位置
 * 正好等于：rec[index].k == k
 * 在区间：rec[index].k < k < rec[index+1].k
 */
static int find_key(struct page_s *p, uint64_t k) {
    // 中间 低位 高位 二分查找
    int mi, lo, hi;
    // 低位=0
    lo = 0;
    // 现存的最高位
    hi = p->h.record_num - 1;

    // 向新树根插入时，pos 传入的是 -1
    // key 小于 当前页的 第0位置的值，那就把当前key插入到最首位
    if (p->h.record_num <= 0 || k < p->rec[lo].k) {
        return -1;
    }

    // key 大于 等于 高位的 key
    if (k >= p->rec[hi].k) {
        return hi;
    }

    while (lo <= hi) {
        mi = (lo + hi) / 2;
        if (k == p->rec[mi].k) {
            return mi;
        }
        if (k > p->rec[mi].k) {
            if (k < p->rec[mi + 1].k) {
                return mi;
            } else {
                lo = mi + 1;
            }
        } else {
            hi = mi - 1;
        }
    }
    kvdb_assert(0);
    return -1;
}

/* insert a record into a page */
// pos 的作用 加速对比
// 1. 没有页分裂，只是向一个页面中插入记录: pos不定
// 2. A页面分裂后，产生了新页面B，那么页面B中的首个记录，需要向 A页面的父节点 插入指向自己的记录: pos不定
static int insert_rec(kvdb_t d, pg_t pg, struct page_s *p, int pos, struct record_s *rec) {
    int i;
    int ret = OK;

    //fprintf(stderr, "insert_rec(): p=%p, (%s) pos=%d, rec=(%lu, %lu)\n",
    //		p, (p->h.flags&PAGE_LEAF ? "leaf" : "branch"), pos, rec->k, rec->v);
    // 没有记录被插入 直接插入 直接返回，pos = -1
    if (p->h.record_num == 0) {
        // 没有做排序啊
        p->rec[0].k = rec->k;
        p->rec[0].v = rec->v;
        p->h.record_num = 1;
        mark_page_dirty(d, pg);
        return REC_INSERTED;
    }

    kvdb_assert(p->h.record_num < RECORD_NUM_PG);

    // 如果想要插入的位置中的 k 小于 入参中的 k
    // p->rec[pos].k 这个值会不会为 null 啊？
    if (rec->k > p->rec[pos].k) {// 插入的记录大
        kvdb_assert(pos == p->h.record_num - 1 || p->rec[pos].k < p->rec[pos + 1].k);
        // 把 pos+1 后的所有记录向后推移一位
        for (i = p->h.record_num; i > pos + 1; i--) {
            p->rec[i].k = p->rec[i - 1].k;
            p->rec[i].v = p->rec[i - 1].v;
        }
        // 将 rec 放入 pos+1 处
        p->rec[pos + 1].k = rec->k;
        p->rec[pos + 1].v = rec->v;
        p->h.record_num++;
        ret = REC_INSERTED;
    } else if (rec->k == p->rec[pos].k) {// 相等
        /* If the page is a branch in the tree, its record should not be replaced */
        kvdb_assert((p->h.flags & PAGE_LEAF) != 0);
        /* replace the value */
        p->rec[pos].v = rec->v;
        ret = REC_REPLACED;
    } else if (rec->k < p->rec[pos].k && pos == 0) {// 插入的记录小 && 在 0 位置
        // 将所有记录向后偏移一位
        for (i = p->h.record_num; i > 0; i--) {
            p->rec[i].k = p->rec[i - 1].k;
            p->rec[i].v = p->rec[i - 1].v;
        }
        p->rec[0].k = rec->k;
        p->rec[0].v = rec->v;
        p->h.record_num++;
        ret = REC_INSERTED;
    } else {// rec->k < p->rec[pos].k && pos != 0: 在页分裂情况下，这个父节点中的pos位置的k值 不太可能 大于 子节点中的k值，因为父节点中一直保存的是页面中最小的k值
        /* rec->k should not be less than p->rec[pos].k */
        // rec->k 不应小于 p->rec[pos].k
        kvdb_assert(0);
    }
    mark_page_dirty(d, pg);
    return ret;
}

/* 
 * split current page into two pages and insert a record which pointer to the new one into parent page.
 * This function may be the most complex in the kv-db, so make sure you have understood it before you try to change it.
 * 页分裂，精彩！
 */
static void bpt_split(kvdb_t d, pg_t ppg, struct page_s *parent, int _ppos, struct page_s *curr) {
    struct page_s *p;
    gpid_t new_gpid;
    pg_t pg, up_pg;
    struct page_s *up = parent;
    int need_to_put = 0;
    int i, j;
    int ppos = _ppos;
    int half;
    struct record_s rec;

    /* If the current page is root, then we need make a new root page and
     * reduce the old root to be an inferior to the new one as a leaf.
     * 如果当前页面是根，那么我们需要创建一个新的根页面，并将旧根作为新根的叶子节点
     */
    if (parent == NULL) {// ppg == NULL
        rec.k = curr->rec[0].k;
        rec.v = d->h->root_gpid;// 记录的v是全局唯一 ID
        // 创建一个新的树根 page 非叶子节点
        bpt_make_root(d, 0);// d->h->root_gpid = new_root_gpid
        // 此时 新页面 已经产生了，并且和索引进行链接了
        up_pg = get_page(d, d->h->root_gpid);
        // 新页面的 buf
        up = get_page_buf(d, up_pg);
        // 将当前page中的首记录k 插入到 父节点中
        // 内存中的索引、实际的物理page，-1
        insert_rec(d, up_pg, up, -1, &rec);
        // 父节点索引 是否需要插入到 free 链表中
        need_to_put = 1;
        // parent pos = 0
        ppos = 0;
    } else {// 不是 根节点，其他类型节点的话都有父节点
        // 保存一下
        up = parent;
        up_pg = ppg;
    }

    /*
     * allocate a new brother page and copy the last half records in the current page to
     * the new one.
     * 创建兄弟平层的 page 页面
     */
    new_gpid = alloc_page(d);
    // 新 page 索引
    pg = get_page(d, new_gpid);
    // 新 page buf
    p = get_page_buf(d, pg);
    // 当前 page 的一半 数量
    half = curr->h.record_num / 2;
    // 将 curr page 一半记录转移到 新 page 中
    for (i = half; i < curr->h.record_num; i++) {
        j = i - half;
        p->rec[j].k = curr->rec[i].k;
        p->rec[j].v = curr->rec[i].v;
    }
    p->h.flags = curr->h.flags;
    p->h.next = curr->h.next;
    p->h.record_num = curr->h.record_num - half;
    curr->h.record_num = half;
    curr->h.next = new_gpid;// curr < p

    /* insert new record which pointed to the new page into the parent page */
    // 在父节点中 插入以一个 指向新 page 页面的记录
    // 作为新页面的首条记录
    rec.k = p->rec[0].k;
    rec.v = (uint64_t) new_gpid;// 新节点ID
    insert_rec(d, up_pg, up, ppos, &rec);

    /* release new page */
    // 新 pg 创建完 放到 free 列表中
    put_page(d, pg);
    // 父节点需要放入 free 列表中
    if (need_to_put) {
        /* release parent page if it is necessary */
        put_page(d, up_pg);
    }
}

/* 
 * bpt_insert -- insert a record into a B+ Tree
 * ppg    - maybe is NULL when first put rec to kv
 * parent - maybe is NULL when first put rec to kv
 * ppos - the position of current page record in parent page 当前页面记录在父页面中的位置
 *        if the parent is root, then ppos == -1
 * curr -- the current page's gpid
 * rec  -- the record to be inserted
 * 
 * return OK, success
 *
 * return PAGE_SPLITED, means the caller should the function again because the page is full 
 * and it split into two pieces 表示调用方应再次使用该函数，因为页面已满并且分为两部分
 */
static int bpt_insert(kvdb_t d, pg_t ppg, struct page_s *parent, int ppos, gpid_t curr, struct record_s *rec) {
    struct page_s *p;
    pg_t pg;
    int pos;
    int ret;

    //fprintf(stderr, "bpt_insert(): gpid=%lu, ppos=%d, parent=%p, rec=(%lu, %lu)\n",
    //		curr, ppos, parent, rec->k, rec->v);
    // 根据页面ID 获得 页面索引
    pg = get_page(d, curr);
    // 根据页面索引获得 页面buf
    p = get_page_buf(d, pg);
    // 当前页面记录数量满了，需要页分裂
    if (p->h.record_num >= RECORD_NUM_PG) {
        bpt_split(d, ppg, parent, ppos, p);
        put_page(d, pg);
        return PAGE_SPLITED;
    }

    // 当前节点是叶子节点
    if (p->h.flags & PAGE_LEAF) {
        // 找到这个 key 的指向: 当页面中没有记录时返回-1; 当有记录时返回小于等于k的pos;
        pos = find_key(p, rec->k);
        // 此时 pos 可能正好找到，也或许没有找到，返回的是最小值
        if (pos < 0) {
            pos = 0;
        }
        // 正常插入，会排序插入，pg p 都不为空
        ret = insert_rec(d, pg, p, pos, rec);
    } else {// 非叶子节点, 需要递归向下找叶子节点
        int tries = 0;
        do {
            // 在当前的非叶子节点 找到一个 指向，小于等于k的指针页面
            pos = find_key(p, rec->k);
            // 此时 pos 可能正好找到，也或许没有找到
            if (pos < 0) {
                pos = 0;
            }
            ret = bpt_insert(d, pg, p, pos, (gpid_t) p->rec[pos].v, rec);
            tries++;
        } while (ret == PAGE_SPLITED);
        kvdb_assert(tries <= 2);
    }

    // 放到 free 列表中
    put_page(d, pg);
    // REC_REPLACED or REC_REPLACED
    return ret == REC_REPLACED ? REC_REPLACED : REC_INSERTED;
}

// 数据库添加记录操作
int kvdb_put(kvdb_t d, uint64_t k, uint64_t v) {
    int tries = 0;
    struct record_s rec;
    int ret;
    // 判断 B+Tree 树深度
    // 首次插入就创建树根 叶子类型
    if (d->h->level == 0) {
        // 创建一个 树根页面 page 是叶子节点
        bpt_make_root(d, 1);
    }
    rec.k = k;
    rec.v = v;
    do {
        // 一开始 并不知道 具体向哪个页插入数据，因此 父节点都是NULL，传入根节点，进行搜索
        ret = bpt_insert(d, NULL, NULL, -1, d->h->root_gpid, &rec);
        tries++;
        kvdb_assert(tries <= 2);
    } while (ret == PAGE_SPLITED);

    if (ret != REC_REPLACED) {
        d->h->record_num++;
    }

    return 0;
}

// 当前物理页中删除 记录
void delete_rec(struct page_s *p, int pos) {
    int i;

    if (p->h.record_num == 1) {
        // 变相的 地址复用
        p->h.record_num = 0;
        return;
    }
    // 否则的话，将pos之后的向前挪一位
    for (i = pos; i < p->h.record_num - 1; i++) {
        p->rec[i].k = p->rec[i + 1].k;
        p->rec[i].v = p->rec[i + 1].v;
    }
    p->h.record_num--;
}

/* 
 * return OK            -- success, nothing following step is needed to do. 记录删除成功，页中还有数据
 *        PAGE_DELETED  -- success, the page is empty and has been deleted, so the entry which 
 *                         pointed to that page is needed to delete. 记录删除成功，并且页为空了
 *        REC_NOT_FOUND -- there is not the record to be deleted.  没有找到数据
 *  
 */
int bpt_del(kvdb_t d, gpid_t gpid, uint64_t k) {
    struct page_s *p;
    pg_t pg;
    int pos, ret = OK;

    pg = get_page(d, gpid);
    p = get_page_buf(d, pg);
    // 从当前页中 找到 小于等于当前k的 pos
    pos = find_key(p, k);

    // 如果当前不是叶子节点，说明需要继续向下找
    if ((p->h.flags & PAGE_LEAF) == 0) {
        // 递归向下找
        ret = bpt_del(d, (gpid_t) p->rec[pos].v, k);
        // 假如说 记录 页都空了 那么需要父节点也删除对应的指针
        if (ret == PAGE_DELETED) {
            // 当前节点中删除这个节点的 指针
            delete_rec(p, pos);
            // 说明 当前页也需要进行删除
            if (p->h.record_num == 0) {
                goto delete_page;
            }
        }
    } else {
        // 叶子节点
        if (p->rec[pos].k != k) {
            ret = REC_NOT_FOUND;
        } else {
            // 准确删除
            delete_rec(p, pos);
            if (p->h.record_num == 0) {
                goto delete_page;
            } else {
                ret = OK;
            }
        }
    }

    // 不需要进行删除页面
    put_page(d, pg);
    return ret;        /* OK or NOT_FOUND */

    delete_page:
    put_page(d, pg);
    free_page(d, gpid);
    return PAGE_DELETED;
}

// 删除一个key
int kvdb_del(kvdb_t d, uint64_t k) {
    int ret;
    // 根节点存储
    kvdb_dump_page(d, d->h->root_gpid);
    // B+Tree 中删除节点
    ret = bpt_del(d, d->h->root_gpid, k);
    //
    if (ret == PAGE_DELETED) {
        d->h->level = 0;
        d->h->root_gpid = GPID_NIL;
    }
    if (ret == PAGE_DELETED || ret == OK) {
        d->h->record_num--;
    }
    return ret == REC_NOT_FOUND ? -1 : 0;
}

// kvdb_get(cursor_s NULL);
int bpt_search(kvdb_t d, gpid_t gpid, uint64_t k, struct record_s *rec, struct cursor_s *cs) {
    struct page_s *p;
    pg_t pg;
    int pos;
    gpid_t next;
    int ret;
    //
    pg = get_page(d, gpid);
    //
    p = get_page_buf(d, pg);
    //
    pos = find_key(p, k);//可能会等于 -1
    /*
    fprintf(stderr, "bpt_search(): gpid=%lu(%s), k=%lu, pos=%d, \n", gpid, (p->h.flags&PAGE_LEAF ? "leaf" : "branch"), k, pos);
    if ((p->h.flags & PAGE_LEAF) == 0) {
        _kvdb_dump_page(gpid, p);
    }*/

    // 当前节点是 叶子数据节点
    if ((p->h.flags & PAGE_LEAF) != 0) {
        // 说明没有找到 k
        if (pos < 0) {
            ret = REC_NOT_FOUND;
            goto end;
        }
        // 准确命中
        if (rec != NULL && p->rec[pos].k == k) {
            rec->k = p->rec[pos].k;
            rec->v = p->rec[pos].v;
        }
        // p->rec[pos].k != k || k > hi
        ret = (p->rec[pos].k == k ? FOUND_EXACT : FOUND_GREATER);
        goto end;
    }

    // 非叶子节点 && pos < 0 => 说明没有相关数据
    if (pos < 0) {
        pos = 0;
    }

    // 下一个 page 页
    next = (gpid_t) p->rec[pos].v;
    //
    put_page(d, pg);
    // 递归去查找
    return bpt_search(d, next, k, rec, cs);

    end:
    // 迭代器不为空，把最后存在k的page信息返回回去，方便迭代，
    if (cs != NULL) {
        cs->gpid = gpid;
        cs->pg = pg;
        cs->p = p;
        cs->pos = pos;
    } else {
        // 迭代器为空
        put_page(d, pg);
    }
    return ret;
}

/* 
 * return 0 -- we have found it
 *       -1 -- have not fount it
 */
int kvdb_get(kvdb_t d, uint64_t k, uint64_t *v) {
    int ret; // 查询结果
    struct record_s rec; // value 结果
    //
    kvdb_dump_page(d, d->h->root_gpid);
    // 迭代器为 null
    ret = bpt_search(d, d->h->root_gpid, k, &rec, NULL);
    if (ret == FOUND_EXACT) {
        *v = rec.v;
        return 0;
    }
    return -1;
}

// 存储 迭代器
void dump_cursor(kvdb_t db, cursor_t cs) {
    fprintf(stderr, "cursor: cs->gpid=%lu, cs->pg=%p, cs->p=%p, cs->pos=%d\n", cs->gpid, cs->pg, cs->p, cs->pos);
    _kvdb_dump_page(cs->gpid, cs->p);
}

// 1️⃣ 简单的找到 start_key ，并拿到 有start_key的page页信息 赋值给迭代器
cursor_t kvdb_open_cursor(kvdb_t db, uint64_t start_key, uint64_t end_key) {
    struct cursor_s *cs;

    cs = malloc(sizeof(*cs));
    kvdb_assert(cs != NULL);

    cs->start_key = start_key;
    cs->end_key = end_key;

    // 当前B+Tree中没有数据
    if (db->h->record_num == 0 && db->h->root_gpid == GPID_NIL) {
        cs->gpid = GPID_NIL;
        cs->pg = NULL;
        cs->p = NULL;
        cs->pos = -1;
        return cs;
    }
    /*
     * the 'pos' in cursor would be -1 if there is no record could be returned,
     * so we do not care about the return value in this case.
     */
    // 试图装扮 cs 迭代器
    bpt_search(db, db->h->root_gpid, start_key, NULL, cs);
    return cs;
}

// 可能会有 start_key 记录，也有可能没有start_key记录
// 2️⃣ 迭代找寻
int kvdb_get_next(kvdb_t db, cursor_t cs, uint64_t *k, uint64_t *v) {
    if (cs->gpid == GPID_NIL) {
        return -1;
    }

    // 到当前 page 的最后一个记录了
    if (cs->pos >= cs->p->h.record_num) {
        // 判断是否有下一个page页
        if (cs->p->h.next == GPID_NIL) {
            return -1;
        }
        // 当前 page 还有下一页
        put_page(db, cs->pg);
        cs->gpid = cs->p->h.next;
        cs->pg = get_page(db, cs->gpid);
        cs->p = get_page_buf(db, cs->pg);
        // 下一页 从头开始 遍历 很合理
        cs->pos = 0;
    }

    kvdb_assert((cs->p->h.flags & PAGE_LEAF) != 0);
    kvdb_assert(cs->p->h.record_num > 0);// 下一页既然存在，那就得有数据，不存在，就灭有数据，看删除记录的逻辑
    kvdb_assert(cs->pos < cs->p->h.record_num);

    // 什么情况才会 等于 -1 ？没有start_key记录的情况
    if (cs->pos == -1) {
        cs->pos = 0;
    }

    // cs->pos : 当前页中 相关k的最小索引处
    // 当前页中的 索引处 的 k >= 终末k，说明不存在 start_key 相关记录
    if (cs->p->rec[cs->pos].k >= cs->end_key) {
        return -1;
    }

    *k = cs->p->rec[cs->pos].k;
    *v = cs->p->rec[cs->pos].v;
    cs->pos++;

    return 0;
}

// 关闭迭代器
void kvdb_close_cursor(kvdb_t db, cursor_t cs) {
    if (cs->gpid != GPID_NIL) {
        put_page(db, cs->pg);
    }
    free(cs);
}

